﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LiKou.数据结构
{
    /// <summary>
    /// 53.
    /// 给你一个整数数组 nums ，
    /// 请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。\
    /// 子数组 是数组中的一个连续部分。
    /// </summary>
    internal class Sub_53
    {
        int[] nums = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        public static int Go(int[] nums)
        {
            int currentSum = 0;int maxNum = nums[0];
            foreach (var num in nums)
            {
                currentSum = Math.Max(currentSum + num, num);//如果前面的和小于当前值，就以当前值作为开始
                maxNum = Math.Max(maxNum, currentSum);
            }
            return maxNum;
        }

        /// <summary>
        /// 超时X
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int Go2(int[] nums)
        {
            int maxNum = nums[0];
            for (int i = 0; i < nums.Length; i++)
            {
                int sum = 0;
                for (int j = i; j < nums.Length; j++)
                {
                    sum += nums[j];
                    maxNum= Math.Max(maxNum, sum);
                }
            }
            return maxNum;
        }
    }
}
